\documentclass[main]{subfiles} 

\begin{document}
	\section{01BFS复习【20250117】}
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1332}{洛谷-P1332}}
	所有已经感染的格子感染时间为0，然后直接BFS向四周扩展，求出所有格子感染时间。最后输出b个领主所在格子的感染时间即可。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P10234}{洛谷-P10234}}
	初始将所有的$dist$设为$\infty$,将左上角的$dist$置为0，同时放入$queue$中，然后BFS每次扩展的时候注意判断相邻的两个格子数值不等。若右下角的$dist$仍为$\infty$则无解，否则根据dist从右下角开始倒推出一条路径来。
	
	\subsection{\href{https://vjudge.net/problem/AtCoder-abc305\_e\#author=DeepSeek\_zh}{AtCoder-abc305\_e}}
	初始将所有的$dist$设为-1，$dist[p_i]=h_i$，若$e(u,v)$存在，则$dist[v] = max\{dist[v],dist[u]-1\}$。求$dist$的时候可以开$max\{h_i\}+1$个$queue$，BFS扩展出的$dist[u] = h$的点扔到$queue[h]$中去即可。最后的答案为所有$dist$非负的点。
	
	\subsection{\href{https://vjudge.net/problem/AtCoder-abc176\_d\#author=DeepSeek\_zh}{AtCoder-abc176\_d}}
	初始将所有的$dist$设为$\infty$，将$dist[C_h][C_w]$置为0。若通过方式A来转移的话，$dist$不变；若使用魔法通过方式B来转移的话，$dist$需要$+1$。通过开多个$queue$来BFS，$dist[x][y]=d$的状态扔到$queue[d]$中，实际实现的时候因为$dist$最多只会加1可以只开两个$queue$滚动。最后判一下$dist[D_h][D_w]$是否为$\infty$即可。
	
	\hypertarget{CodeForces-1340C}{}
	\subsection{\href{https://vjudge.net/problem/CodeForces-1340C\#author=DeepSeek\_zh}{CodeForces-1340C}}
	通过观察可以发现：小伙达到某个安全岛时，绿灯已经过去了多久决定了小伙后续可以到达哪些安全岛。
	
	所以我们可以用$(pos,time)$来表示状态，$dist[pos][time]$表示经过多少个$r+g$的红绿灯周期从$(0,0)$到达$(pos,time)$，初始$dist[0][0]=0$，其余为$\infty$。还是01BFS的经典做法，开两个$queue$滚动使用：$(now,now\_time)$状态转移的时候,若$now\_time + |pos[next]-pos[now]|<g$则转移到$(next,now\_time + |pos[next]-pos[now]|)$代价为0，$(next,now\_time + |pos[next]-pos[now]|)$放入当前$queue$；若$now\_time + |pos[next]-pos[now]|=g$则转移到$(next,0)$代价为1,$(next,0)$放入另外一个$queue$；若$now\_time + pos[next]-pos[now]>g$则无法转移。
	
	特别注意$time=0$的时候不需要额外等一次红灯，否则会WA 18，所以最后的答案为$min\{dist[m][0]*(r+g)-r,dist[m][i]*(r+g)+i|0<i<g\}$。
	
	\hypertarget{CodeForces-1749E}{}
	\subsection{\href{https://vjudge.net/problem/CodeForces-1749E\#author=DeepSeek\_zh}{CodeForces-1749E}}
	题目要求通过增加仙人掌让最上一行到最下一行，不存在任何一条路径使得：
	\begin{itemize}
		\item 路径中相邻两个格子必须上下左右相连
		\item 路径经过的格子里都不能有仙人掌
	\end{itemize}
	
	这个要求等价于从最左一列到最右一列存在一条路径：
	\begin{itemize}
		\item 路径中相邻两个格子刚好共一个顶点
		\item 路径经过的格子里都有仙人掌
	\end{itemize}
	
	这是一个典型的01BFS问题，特别注意：
	\begin{itemize}
		\item 由于01BFS的特性不一定只会从左往右走
		\item 因为存在代价为0的转移，只根据$dist$是无法构造出方案的，必须记录最优转移
	\end{itemize}
	
	\hypertarget{CodeForces-821D}{}
	\subsection{\href{https://vjudge.net/problem/CodeForces-821D\#author=DeepSeek\_zh}{CodeForces-821D}}
	新建一个图$g$，对于网格上每个亮着的点$u(x,y)$建一个点，对于每一行$R_i$每一列$C_j$分别建一个点表示当前点亮的是哪行哪列。
	
	连边情况对于每一个$u(x,y)$：
	\begin{itemize}
		\item 若$v\in \{ (x-1,y),(x+1,y),{x,y-1},{x,y+1}\}$,且v是亮着的，则$e(u,v)=e(v,u)=0$
		\item 点亮第$t(x-1\leq t \leq x+1)$行，则$e(u,R_t)=1,e(R_t,u)=0$
		\item 点亮第$t(y-1\leq t \leq y+1)$列，则$e(u,C_t)=1,e(C_t,u)=0$
	\end{itemize}
	
	最后若$(n,m)$不是亮着的，则加上一个点$u^{'}(n,m),u^{'}$只连$e(u^{'},R_n)=1,e(R_n,u^{'})=0,e(u^{'},C_m)=1,e(C_m,u^{'})=0$这四条边
	
	在这个$g$上用01-BFS求$(1,1)$对应的点$Begin$到$(n,m)$对应的点$End$的最短路即可。
	
	\hypertarget{洛谷-P3956}{}
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P3956}{洛谷-P3956}}
	一开始没有想清楚到底该怎么处理无色的格子，出现了以下的错误:
	\begin{itemize}
		\item 考虑直接跳过无色的格子走到有色的格子，但是要特判$(M,M)$也是无色的情况，而且走两步需要考虑8个格子，不大容易想清楚
		\item 没有考虑清楚无色格子染色后走的代价
	\end{itemize}
	
	最后的解法是对于每个有色格子建立一个点，对于每个周围有有色格子的无色格子根据染色的不同拆出至多不超过4个点。对于所有的点按照转移的代价连边，特别要注意当$u,v$中有空白格子时$e(u,v)$  和 $e(v,u)$的边权会不同。建完图注意到边权最多为3，可以开多个队列分别BFS。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-1941G\#author=GPT\_zh}{CodeForces-1941G}}
	一开始我的想法是用$(station\_id,line\_id)$作为状态，然后跑01BFS。这样做在地铁线和地铁站都特别多的情况下状态数就有点爆炸了，于是TLE 47。
	
	看了题解才发现我没有充分利用地铁线路在图中形成一个连通子图这个条件，题解提供的做法是建一个二分图：左边顶点是地铁站，右边顶点是地铁线。若地铁线$u$经过地铁站$v$，则连两条权值为1的边：$e(v,u), e(u,v)$，最后的答案为$b$和$e$之间的最短路除以2，最短路用普通的BFS即可求解。
	
	\subsection{Summary}
	\begin{itemize}
		\item 01BFS因为有两类转移，所以一定要把状态转移考虑完全，如果建新图能够更加清晰要果断建图，如：\hyperlink{CodeForces-821D}{CodeForces-821D}和\hyperlink{洛谷-P3956}{洛谷-P3956}
		\item 01BFS因为状态和答案之间是需要一步转化的，所以要考虑清楚边界情况，如：\hyperlink{CodeForces-1340C}{CodeForces-1340C}
		\item 01BFS因为存在代价为0的转移，所以对于需要输出方案的题目时必须要在转移时记录最优转移的方案，如：\hyperlink{CodeForces-1749E}{CodeForces-1749E}
	\end{itemize}
\end{document}